# 对于一个有序列表，依次取半，直到找到目标

def binary_search(li: list, val) -> int:
    left = 0
    right = len(li) - 1
    while left <= right:
        mid = (left + right) // 2
        if li[mid] == val:
            return mid
        elif val < li[mid]:
            # 目标值在中间值的左边
            right = mid - 1
        elif li[mid] < val:
            # 目标值在中间值的右边
            left = mid + 1
    return -1


def binary_search_v2(li: list, val, left=None, right=None) -> int:
    if left is None:
        left = 0
    if right is None:
        right = len(li) -1
    if left > right:
        return -1
    mid = (left + right) // 2
    if li[mid] == val:
        return mid
    elif val < li[mid]:
        # 目标值在中间值的左边
        return binary_search_v2(li, val, left, mid - 1)
    elif li[mid] < val:
        # 目标值在中间值的右边
        return binary_search_v2(li, val, mid + 1, right)

